import java.util.Arrays;

public class lengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        //最长递增子序列
        // 初始化一个与nums数组长度相同的dp数组，用于存储到当前位置的最长递增子序列长度
        int[] dp = new int[nums.length];

        // 遍历nums数组，初始化dp数组的每个元素为1，因为任何元素自成一个递增子序列
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            // 内层循环遍历当前元素之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素大于前一个元素，表示可以形成递增子序列
                if (nums[i] > nums[j]) {
                    // 更新dp[i]为当前元素作为结尾的最长递增子序列长度
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 返回dp数组中的最大值，即为整个数组的最长递增子序列长度
        return Arrays.stream(dp).max().getAsInt();

    }
}
